package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * <a href='https://leetcode.cn/problems/remove-letter-to-equalize-frequency/'>删除字符使频率相同</a>
 * <p>
 * 给你一个下标从 0 开始的字符串 word ，字符串只包含小写英文字母。你需要选择 一个 下标并 删除 下标处的字符，使得 word 中剩余每个字母出现 频率 相同。
 * 如果删除一个字母后，word 中剩余所有字母的出现频率都相同，那么返回 true ，否则返回 false 。
 * <b>注意：</b>
 * <li>字母 x 的 频率 是这个字母在字符串中出现的次数。</li>
 * <li>你 必须 恰好删除一个字母，不能一个字母都不删除。</li>
 * </p>
 * <pre>
 * 示例 1：
 *      输入：word = "abcc"
 *      输出：true
 *      解释：选择下标 3 并删除该字母，word 变成 "abc" 且每个字母出现频率都为 1 。
 *
 * 示例 2：
 *      输入：word = "aazz"
 *      输出：false
 *      解释：我们必须删除一个字母，所以要么 "a" 的频率变为 1 且 "z" 的频率为 2 ，要么两个字母频率反过来。所以不可能让剩余所有字母出现频率相同。
 * </pre>
 * <b>提示：</b>
 * <li>2 <= word.length <= 100</li>
 * <li>word 只包含小写英文字母。</li>
 *
 * @author c2b
 * @since 2023/4/14 15:13
 */
public class LC2423EqualFrequency_S {

    public boolean equalFrequency(String word) {
        char[] charArray = word.toCharArray();
        Map<Character, Integer> hashMap = new HashMap<>();
        for (char c : charArray) {
            hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
        }
        Set<Character> keySet = hashMap.keySet();
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (Character key : keySet) {
            treeMap.put(hashMap.get(key), treeMap.getOrDefault(hashMap.get(key), 0) + 1);
        }
        if (treeMap.size() > 2) {
            return false;
        } else if (treeMap.size() == 1) {
            return hashMap.size() == 1 || treeMap.containsKey(1);
        } else if (treeMap.containsKey(1) && treeMap.get(1) == 1) {
            return true;
        } else if (treeMap.lastKey() - treeMap.firstKey() == 1) {
            return treeMap.lastEntry().getValue() == 1;
        }
        return false;
    }
}
